//
// Created by Administrator on 2021/9/9.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
    // blank 返回长度为 n 的由空格组成的字符串
    string blank(int n) {
        return string(n, ' ');
    }

    // join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串
    string join(vector<string> &words, int left, int right, string sep) {
        string s = words[left];
        for (int i = left + 1; i < right; ++i) {
            s += sep + words[i];
        }
        return s;
    }

public:
    vector<string> fullJustify(vector<string> &words, int maxWidth) {
        vector<string> ans;
        int right = 0, n = (int) words.size();
        while (true) {
            int left = right; // 当前行的第一个单词在 words 的位置
            int sumLen = 0; // 统计这一行单词长度之和
            // 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格
            while (right < n && sumLen + words[right].length() + right - left <= maxWidth) {
                sumLen += words[right++].length();
            }

            // 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格
            if (right == n) {
                string s = join(words, left, n, " ");
                ans.emplace_back(s + blank(maxWidth - s.length()));
                return ans;
            }
            // 这一行的单词数
            int numWords = right - left;
            // 这一行的空格总数
            int numSpaces = maxWidth - sumLen;

            // 当前行只有一个单词：该单词左对齐，在行末填充剩余空格
            if (numWords == 1) {
                ans.emplace_back(words[left] + blank(numSpaces));
                continue;
            }
            // 当前行不只一个单词
            // 平均每个单词之间的空格数
            int avgSpaces = numSpaces / (numWords - 1);
            // 多出来的空格数
            int extraSpaces = numSpaces % (numWords - 1);
            // 对前extraSpace个单词，应该多加1个空格
            string s1 = join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1)); // 拼接额外加一个空格的单词
            // 剩下的  都是间隔avg个空格
            string s2 = join(words, left + extraSpaces + 1, right, blank(avgSpaces)); // 拼接其余单词
            s1 += blank(avgSpaces) + s2;
            ans.emplace_back(s1);
        }
    }
};

int main() {
    vector<string> words{"This", "is", "an", "example", "of", "text", "justification."};
    Solution solution;
    vector<string> ans = solution.fullJustify(words, 16);
    for (string &x: ans)
        cout << x << endl;
    return 0;
}
